﻿#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>

//给定⼀个整数数组, 数组中有⼀个数出现了⼀次, 其他数出现了两次, 请找出只出现了⼀次的数。


//思路一
//直接双层循环，
//从前往后统计元素出现的次数，遇到出现次数为1的，直接返回。这个时间复杂度为O(n ^ 2)，部分测试⽤例过不了，只能过掉80% 。
int SingleNumber1(int* nums, int numsLen)
{
	int res = 0;
	for (int i = 0; i < numsLen; i++)
	{
		int flag = 0;
		for (int j = 0; j < numsLen; j++)
		{
			if (i != j && nums[i] == nums[j])
			{
				flag = 1;
				break;
			}
		}
		if (flag == 0)
		{
			res = nums[i];
			break;
		}
	}
	return res;
}


//思路二
//按位异或的逻辑的，相同⼆进制位下，⼆进制相同为0，相异为1，
//⽽当两个数相同时，那么他的所有⼆进制位上相同位置都是相同的，
//那么根据异或原理，两个相同数异或为0了，⽽0跟任意⼀个数异或是本⾝，根据这个性质求解。
int SingleNumber2(int* nums, int numsLen)
{
	int result = 0;
	for (int i = 0; i < numsLen; i++)
	{
		result ^= nums[i];
	}
	return result;
}



int main()
{
	int arr[] = { 1,2,3,6,8,4,3,4,1,2,8,5,9,6,9};
	int sz = sizeof(arr) / sizeof(arr[0]);
	/*int res = SingleNumber1(arr, sz);*/
	int res = SingleNumber2(arr, sz);
	printf("%d\n", res);
	return 0;
}